//
// Created by Administrator on 2021/11/12.
//
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50 //自定义最大长度
#define ElemType char //自定义ElemType类型
/*定义顺序栈*/
typedef struct {
    ElemType data[MaxSize];//存放栈中的元素
    int top;//栈顶指针
} SqStack;

/*初始化栈*/
void InitStack(SqStack &S) {
    S.top = -1;//初始化栈顶指针
}

/*判断栈空*/
bool StackEmpty(SqStack S) {
    return S.top == -1;
}

/*新元素入栈*/
bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) {
        return false;//栈满，报错
    }
    S.top = S.top + 1;//指针先加1
    S.data[S.top] = x;//新元素入栈
    return true;
}

/*出栈操作*/
bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) {
        return false;//栈空，报错
    }
    x = S.data[S.top--];//栈顶元素先出栈s.top = s.top - 1;/指针再减1
    return true;
}

/*读栈顶元素*/
bool GetTop(SqStack S, ElemType &x) {
    if (S.top == -1) {
        return false; //栈空，报错
    }
    x = S.data[S.top];//x记录栈顶元素
    return true;
}

void TestStack() {
    SqStack s;//声明一个顺序栈(分配空间)InitStack(S);
    // ...后续操作...
}

/*定义共享栈*/
typedef struct {
    ElemType data[MaxSize];//存放栈中的元素
    int top0;//栈顶指针
    int top1;
} ShStack;

/*初始化共享栈*/
void InitStack(ShStack &S) {
    S.top0 = -1;//初始化栈顶指针
    S.top1 = MaxSize;
}
/*判满条件：top0+1==top1*/

/*括号匹配
 * 遇到（进栈
 * 遇到）出栈*/
bool bracketCheck(char str[], int length) {
    SqStack S;
    InitStack(S);//初始化一个栈
    for (int i = 0; i < length; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]);//扫描到左括号，入栈
        } else {
            if (StackEmpty(S)) {
                //扫描到右括号，且当前栈空
                return false;// 匹配失败。有括号单身
            }
            char topElem;//用于存储刚弹出的左括号
            Pop(S, topElem);// 栈顶元素出栈
            if (str[i] == ')' && topElem != '(') { return false; }
            if (str[i] == ']' && topElem != '[') { return false; }
            if (str[i] == '}' && topElem != '{') { return false; }
        }
    }
    return StackEmpty(S);//栈空则成功
}

/*中缀转后缀：
 * 模拟计算机出栈入栈的情况：（手算）
 * 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:
①遇到操作数。直接加入后缀表达式。
②遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意:“(”不加入后缀表达式。
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
*/

/*用栈实现中缀表达式的计算:
 * 初始化两个栈，操作数栈和运算符栈
 * 若扫描到操作数，压入操作数栈
 * 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈
 * (期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)
*/

/*递归求阶乘*/
/*计算正整数n!*/
int factorial(int n) {
    if (n == 0 || n == 1) { return 1; }
    else { return n * factorial(n - 1); }
}

/*递归算法求斐波那契数列*/
int Fib(int n) {
    if (n == 0) { return 0; }
    else if (n == 1) { return 1; }
    else { return Fib(n - 1) + Fib(n - 2); }
}